NC127 最长公共子串

https://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac

暴力法：果然是超时了,,,

func LCS(str1 string, str2 string) string {
    // 创建两个 map 来存储全部的数据
    ans1 := make(map[string]struct{})
    ans2 := make(map[string]struct{})
    process(str1, ans1)
    process(str2, ans2)

    // 把全部子数组比对完成后再逐个比对
    max := math.MinInt32
    result := ""
    for k, _ := range ans1 {
        if _, ok := ans2[k]; ok && max < len(k) {
            max = len(k)
            result = k
        }
    }

    return result
}

func process(str string, ans map[string]struct{}) {
    for i := 0; i < len(str); i++ {
        for j := i; j < len(str); j++ {
            ans[str[i:j + 1]] = struct{}{}
        }
    }
}

动态规划，参考 【数据结构和算法】动态规划解最长公共子串

func LCS(str1 string, str2 string) string {
    maxLastIndex := 0
    maxLength := 0
    // 这个 dp 只是保存 j 一轮循环的递增，历史最大值通过上面两个参数来记录
    dp := make([]int, len(str2)+1) // 这里 + 1 是避免无意义的健壮性判断（判断是否越界）

    for i := 0; i < len(str1); i++ {
        //注意这里是倒叙
        for j := len(str2) - 1; j >= 0; j-- {
            if str1[i] == str2[j] {
                dp[j+1] = dp[j] + 1
                if dp[j+1] > maxLength {
                    //如果遇到了更长的子串，要更新，记录最长子串的长度，
                    //以及最长子串最后一个元素的位置
                    maxLength = dp[j+1]
                    // 注意：因为每一轮都要比较 str2，所以这里记录的最大字串是 str1 的
                    maxLastIndex = i 
                }
            } else {
                //递推公式，两个字符不相等的情况
                dp[j+1] = 0
            }
        }
    }

    // 因为公式为 dp[i][j]=dp[i-1][j-1]+1 全部的下标都前移了一位，所以要加一
    return str1[maxLastIndex - maxLength + 1 : maxLastIndex + 1]
}